1. Field of the Invention
The invention relates to a method and apparatus for providing fault tolerance to a memory and more particularly, to a method and a networking apparatus, such as a switch, a router, or the like, for providing fault tolerance to a memory.
2. Description of the Prior Art
A networking apparatus such as a switch, a router, or the like, is usually employed in the construction of a network of computers. One of the functions of the networking apparatus is to efficiently forward data sent by users (computers on the network) to the data's destination via the ports of the networking apparatus. To accomplish this task, information about host/port relationships must be stored in the memory of the networking apparatus, which is often in the form of a look-up table called a MAC address table.
The MAC address table records the source MAC IDs (SIDs) of incoming packets. If there is an incoming packet to be stored in the MAC memory, a rule called “hashing” is defined for mapping the incoming packet to a specific look-up table entry based on the MAC ID of the incoming packet. Whenever a packet enters the networking apparatus, the networking apparatus picks the destination MAC ID (DID) of this incoming packet and uses the DID to perform hashing. Hashing of the DID maps this DID to a specific entry in the look-up table. The networking apparatus checks the MAC ID stored in this entry to see whether this MAC ID appeared before and has been recorded in the table, this step being called “search”. If the MAC ID stored in this entry is invalid, out of date, or valid but different from the DID under searching, the search result is “missed”. However, if the MAC ID stored in this entry is valid and indeed equal to the DID of the incoming packet, the search result is “hit”. The networking apparatus decides how to forward the packet based on the search result is “missed”, and this packet is a legal packet, this incoming packet will be broadcasted to all the ports except the inbound port. If the search result is “hit”, this incoming packet will be forwarded to the associated port. This step is called “forward”. After forwarding, the network apparatus would try to “learn” the “SID-inbound port” relationship and record the relationship into the look-up table.
One of the aims of utilizing the look-up table in the MAC memory is to prevent unnecessary broadcasting of the incoming packets so that the amount of data transmission can be reduced. Because of the important role the MAC memory storing the host/port relationship plays, current networking apparatus employ only memory free of defects.
However, the fabrication process of memory is by no means perfect. In other words, the yield of memory with no physical defects from the manufacturing process of memory is not 100%. For every batch of memory fabricated, a substantial portion will prove to be defective and as a result be discarded. The end result is a higher manufacturing cost.
As for details concerning hashing schemes, please refer to “a comparison of hashing schemes for address lookup in computer networks”, by Jain, IEEE Transactions on Communications, COM40 (10): 1570–1573, October 1992, which is incorporated herein for reference.